package com.gitee.feizns.explore.data_structure.tree.cus.bt;

import com.gitee.feizns.explore.data_structure.tree.cus.Tree;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collection;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;
import java.util.function.BiConsumer;

/**
 * 二三树
 * @author feizns
 * @since 2019/12/25
 */
public class TwoTFT<K extends Comparable<K>, V> implements Tree<K, V> {

    public static void main(String[] args) {
        TwoTFT<Integer, String> tft = new TwoTFT<>();
        tft.put(1, "1");
        tft.put(2, "1");
        tft.put(3, "1");
        tft.put(4, "1");
        tft.put(5, "1");
        tft.put(6, "1");
        tft.put(7, "1");
        tft.put(8, "1");
        tft.put(9, "1");
        tft.put(10, "1");
        tft.put(11, "1");
        tft.put(12, "1");
        tft.put(13, "1");
        tft.put(14, "1");
        tft.put(15, "1");
        tft.put(16, "1");
        tft.put(17, "1");
        tft.put(18, "1");
        tft.put(19, "1");
        tft.put(20, "1");
        tft.put(21, "1");
//        tft.remove(23);
        tft.remove(2);
        tft.remove(3);
        tft.remove(4);
        tft.remove(5);
        tft.remove(6);
        tft.remove(7);
        tft.remove(8);
        tft.remove(9);
        tft.remove(10);
        tft.remove(11);
        tft.remove(12);
        tft.remove(13);
        tft.remove(14);
        tft.remove(15);
        tft.remove(16);
        tft.remove(17);
        tft.remove(18);
        tft.remove(19);
        tft.remove(20);
        tft.remove(21);
    }

    private int size;

    private Node root;

    @Override
    public int size() {
        return size;
    }

    @Override
    public V get(Object key) {
        K k = (K) key;
        Node tmp = root;
        while ( tmp != null ) {
            List<EntryImpl> entries = tmp.entries;
            int next = entries.size();
            for (int i = 0; i < entries.size(); i++) {
                EntryImpl item = entries.get(i);
                int comp = k.compareTo((K) item.getKey());
                if ( comp < 0 ) {
                    next = i;
                    break;
                } else if ( comp == 0 )
                    return (V) item.getValue();
            }
            tmp = tmp.childNodes.get(next);
        }
        return null;
    }

    @Override
    public V put(K key, V value) {
        NAndV ret = put(root, key, value);
        root = ret.n;
        return ret.v;
    }

    private NAndV put(Node root, K k, V v) {
        if ( root == null ) {
            size++;
            return new NAndV(new Node(new EntryImpl(k, v)), v, true);
        }

        List<EntryImpl> entries = root.entries;
        int next = entries.size();
        for (int i = 0; i < entries.size(); i++) {
            EntryImpl item = entries.get(i);
            int comp = k.compareTo((K) item.getKey());
            if ( comp < 0 ) {
                next = i;
                break;
            } else if ( comp == 0 )
                return new NAndV(root, (V) item.setValue(v));
        }
        Node nextNode = root.childNodes.get(next);
        NAndV ret = put(nextNode, k, v);
        v = ret.v;
        if ( ret.merge )
            root = merge(root, ret.n, next);
        else
            root.childNodes.set(next, ret.n);

        if ( root.entries.size() == 3 ) {
            root = split(root);
            return new NAndV(root, v, true);
        }

        return new NAndV(root, v);
    }

    private Node split(Node node) {
        Node root = new Node(node.entries.get(1));
        Node left = new Node(node.entries.get(0));
        Node right = new Node(node.entries.get(2));
        left.childNodes.set(0, node.childNodes.get(0));
        left.childNodes.set(1, node.childNodes.get(1));
        right.childNodes.set(0, node.childNodes.get(2));
        right.childNodes.set(1, node.childNodes.get(3));
        root.childNodes.set(0, left);
        root.childNodes.set(1, right);
        return root;
    }

    private Node merge(Node node, Node add, int index) {
        node.entries.add(index, add.entries.get(0));
        node.childNodes.set(index, add.childNodes.get(0));
        node.childNodes.add(index + 1, add.childNodes.get(1));
        return node;
    }

    private class NAndV {
        Node n;
        V v;
        boolean merge;
        NAndV(Node n, V v) {
            this.n = n;
            this.v = v;
        }
        public NAndV(Node n, V v, boolean merge) {
            this(n, v);
            this.merge = merge;
        }
    }

    private class ReNAndV {
        Node n;
        V v;
        boolean merge;
        ReNAndV(Node n, V v) {
            this.n = n;
            this.v = v;
        }
        public ReNAndV(Node n, V v, boolean merge) {
            this(n, v);
            this.merge = merge;
        }
    }

    @Override
    public V remove(Object key) {
        ReNAndV nAndV = remove(root, null, (K) key);
        root = nAndV.n;
        return nAndV.v;
    }

    private ReNAndV remove(Node curt, Node parent, K k) {
        if ( curt == null )
            return new ReNAndV(null, null);

        curt = mergeLR(curt, parent);

        List<EntryImpl> entries = curt.entries;
        List<Node> childNodes = curt.childNodes;
        int next = entries.size();
        for (int i = 0; i < entries.size(); i++) {
            EntryImpl item = entries.get(i);
            int comp = k.compareTo((K) item.getKey());
            if ( comp < 0 ) {
                next = i;
                break;
            } else if ( comp == 0 ) {
                V v = (V) entries.get(i).getValue();
                Node right = childNodes.get(i + 1);
                //非叶子节点
                if ( right != null ) {
                    EntryImpl min = min(right);
                    entries.set(i, min);
                    int size = entries.size();
                    ReNAndV nAndV = remove(right, curt, (K) min.getKey());
                    if ( size == entries.size() )
                        childNodes.set(i + 1, nAndV.n);
                    else
                        childNodes.set(i, nAndV.n);
                    v = nAndV.v;
                } else {
                    if ( entries.size() > 1 )
                        entries.remove(i);
                    else if ( entries.size() == 1 ) {
                        if ( parent == null )
                            return new ReNAndV(null, null);
                        int index = sibling(parent.index(curt));
                        Node sibling = parent.childNodes.get(index);
                        if ( sibling.size() > 1 ) {
                            if ( index > i )    //兄弟节点在当前节点的右边
                                leftRotate(curt, parent);
                            else
                                rightRotate(curt, parent);
                        } else {
                            if ( index > i ) {
                                sibling.entries.add(0, parent.entries.get(index - 1));
                                parent.entries.remove(index - 1);
                                parent.childNodes.remove(index - 1);
                                curt = sibling;
                            } else {
                                sibling.entries.add(parent.entries.get(index));
                                parent.entries.remove(index);
                                parent.childNodes.remove(index + 1);
                                curt = sibling;
                            }
                        }
                    }
                    size--;
                }
                return new ReNAndV(curt, v);
            }
        }

        Node nextNode = childNodes.get(next);
        ReNAndV nAndV = remove(nextNode, curt, k);
        if ( nAndV.merge ) {
            next = next > entries.size() ? entries.size() : next;
            entries.add(next, nAndV.n.entries.get(0));
            childNodes.set(next, nAndV.n.childNodes.get(0));
            childNodes.add(next + 1, nAndV.n.childNodes.get(1));
        } else {
            childNodes.set(next, nAndV.n);
        }

        if ( entries.size() > 2 )
            return new ReNAndV(reSplit(curt), nAndV.v, true);

        return new ReNAndV(curt, nAndV.v);
    }

    private Node reSplit(Node curt) {
        if ( curt.size() == 3 ) {
            Node ret = new Node(curt.entries.get(1));
            Node left = new Node(curt.entries.get(0));
            left.childNodes.set(0, curt.childNodes.get(0));
            left.childNodes.set(1, curt.childNodes.get(1));
            Node right = new Node(curt.entries.get(2));
            right.childNodes.set(0, curt.childNodes.get(2));
            right.childNodes.set(1, curt.childNodes.get(3));
            ret.childNodes.set(0, left);
            ret.childNodes.set(1, right);
            return ret;
        } else {
            Node ret = new Node(curt.entries.get(2));
            Node left = new Node(curt.entries.get(0));
            left.entries.add(curt.entries.get(1));
            left.childNodes.set(0, curt.childNodes.get(0));
            left.childNodes.set(1, curt.childNodes.get(1));
            left.childNodes.set(2, curt.childNodes.get(2));
            Node right = new Node(curt.entries.get(3));
            right.childNodes.set(0, curt.childNodes.get(3));
            right.childNodes.set(1, curt.childNodes.get(4));
            ret.childNodes.set(0, left);
            ret.childNodes.set(1, right);
            return ret;
        }
    }

    private EntryImpl min(Node root) {
        Node left = root.childNodes.get(0);
        if ( left != null )
            return min(left);
        return root.entries.get(0);
    }

    private void leftRotate(Node curt, Node parent) {
        int index = parent.index(curt);
        Node right = parent.childNodes.get(index + 1);
        EntryImpl parentVal = parent.entries.get(index);
        curt.entries.set(0, parentVal);
        parent.entries.set(index, right.entries.get(0));
        right.entries.remove(0);
    }

    private void rightRotate(Node curt, Node parent) {
        int index = parent.index(curt);
        Node left = parent.childNodes.get(index - 1);
        EntryImpl parentVal = parent.entries.get(index - 1);
        curt.entries.set(0, parentVal);
        parent.entries.set(index, left.entries.get(left.size() - 1));
        left.entries.remove(left.size() - 1);
    }

    private Node mergeLR(Node curt, Node parent) {
        if ( parent == null ) {
            Node left = curt.childNodes.get(0);
            Node right = curt.childNodes.get(1);
            if ( left != null && right != null && curt.size() == 1 && left.size() == 1 && right.size() == 1 ) {
                List<EntryImpl> entries = new ArrayList<>(Arrays.asList(left.entries.get(0), curt.entries.get(0), right.entries.get(0)));
                Node ret = new Node(entries);
                ret.childNodes.set(0, left.childNodes.get(0));
                ret.childNodes.set(1, left.childNodes.get(1));
                ret.childNodes.set(2, right.childNodes.get(0));
                ret.childNodes.set(3, right.childNodes.get(1));
                return ret;
            }
        } else if ( curt.size() == 1 ) {
            int index = parent.index(curt);
            int siblingIndex = sibling(index);
            Node sibling = parent.childNodes.get(siblingIndex);
            if ( sibling == null )
                return curt;
            if ( sibling.size() > 1 ) {
                if ( index < siblingIndex ) {
                    curt.entries.add(parent.entries.get(index));
                    parent.entries.set(index, sibling.entries.get(0));
                    curt.childNodes.set(2, sibling.childNodes.get(0));
                    sibling.entries.remove(0);
                    sibling.childNodes.remove(0);
                    sibling.childNodes.add(null);
                } else {
                    curt.entries.add(0, parent.entries.get(siblingIndex));
                    parent.entries.set(siblingIndex, sibling.entries.get(sibling.entries.size() - 1));
                    curt.childNodes.add(0, sibling.childNodes.get(sibling.entries.size()));
                    sibling.entries.remove(sibling.entries.size() - 1);
                    sibling.childNodes.remove(sibling.entries.size());
                    sibling.childNodes.add(null);
                }
            } else {
                if ( index < siblingIndex ) {
                    curt.entries.add(parent.entries.get(index));
                    curt.entries.add(sibling.entries.get(0));
                    curt.childNodes.set(2, sibling.childNodes.get(0));
                    curt.childNodes.set(3, sibling.childNodes.get(1));
                    parent.entries.remove(index);
                    parent.childNodes.remove(siblingIndex);
                    parent.childNodes.add(null);
                } else {
                    curt.entries.add(0, parent.entries.get(siblingIndex));
                    curt.entries.add(0, sibling.entries.get(0));
                    curt.childNodes.add(0, sibling.childNodes.get(1));
                    curt.childNodes.add(0, sibling.childNodes.get(0));
                    parent.entries.remove(siblingIndex);
                    parent.childNodes.remove(siblingIndex);
                    parent.childNodes.add(null);
                }
            }
        }
        return curt;
    }

    private int sibling(int index) {
        return index == 0 ? 1 : index - 1;
    }

    @Override
    public void clear() {
        size = 0;
        root = null;
    }

    @Override
    public Set<K> keySet() {
        return null;
    }

    @Override
    public Collection<V> values() {
        return null;
    }

    @Override
    public Set<Entry<K, V>> entrySet() {
        return null;
    }

    private static class EntryImpl<K, V> implements Entry<K, V> {

        private K k;

        private V v;

        public EntryImpl(K k, V v) {
            this.k = k;
            this.v = v;
        }

        @Override
        public K getKey() {
            return k;
        }

        @Override
        public V getValue() {
            return v;
        }

        @Override
        public V setValue(V value) {
            V old = v;
            v = value;
            return old;
        }

    }

    private static class Node {
        private List<EntryImpl> entries = new LinkedList<>();
        private List<Node> childNodes = new LinkedList<>();
        {
            childNodes.add(null);
            childNodes.add(null);
            childNodes.add(null);
            childNodes.add(null);
        }
        public Node(EntryImpl entry) {
            entries.add(entry);
        }
        public Node(List<EntryImpl> entries) {
            this.entries = entries;
        }
        public int size() {
            return entries.size();
        }
        public int index(Node child) {
            return childNodes.indexOf(child);
        }
    }

    @Override
    public void recursiveBeforeEach(BiConsumer<K, V> consumer) {

    }

    @Override
    public void recursiveMiddleEach(BiConsumer<K, V> consumer) {

    }

    @Override
    public void recursiveAfterEach(BiConsumer<K, V> consumer) {

    }

    @Override
    public void recursiveSequenceTraversal(BiConsumer<K, V> consumer) {

    }

    @Override
    public void beforeEach(BiConsumer<K, V> consumer) {

    }

    @Override
    public void middleEach(BiConsumer<K, V> consumer) {

    }

    @Override
    public void afterEach(BiConsumer<K, V> consumer) {

    }

    @Override
    public void sequenceTraversal(BiConsumer<K, V> consumer) {

    }

}
